Recently, the International Organization for Standardization (ISO) adopted a standard protocol for combining one or more "elementary streams" of coded video, audio or other data into a single bitstream suitable for transmission. The standard (ISO 13818), hereinafter referred to as the "MPEG-2 Systems" standard, is described in detail in the MPEG-2 Systems Committee Draft (ISO/IEC JTC1/SC29/WG11/N0601, November, 1993) [hereinafter "MPEG-2 Systems Committee Draft"], which is hereby incorporated by reference. An overview of the MPEG-2 Systems standard is provided in Wasilewski, The MPEG-2 Systems Specification: Blueprint for Network Interoperability (Jan. 3, 1994), which is also hereby incorporated by reference. The MPEG-2 Systems standard provides a syntax and set of semantic rules for the construction of bitstreams containing a multiplexed combination of one or more "programs." A "program" is composed of one or more related elementary streams. An "elementary stream" is the coded representation of a single video, audio or other data stream that shares the common timebase of the program of which it is a member. For example, in the context of a subscription television system, a "program" may comprise a network television broadcast consisting of two elementary streams: a video stream and an audio stream.
As the MPEG-2 Systems standard developed, a two-level packet-based multiplexing scheme emerged. At the first level, each elementary stream to be transmitted, i.e., the coded data for one video, audio or other data stream, is packetized to form a Packetized Elementary Stream (PES). Each PES packet in a given Packetized Elementary Stream consists of a PES packet header followed by a variable length payload containing the coded data of that elementary stream. The Packetized Elementary Stream structure provides a means for packaging subparts of a longer elementary stream into consecutive packets along with associated indicators and overhead information used to synchronize the presentation of that elementary stream with other related elementary streams (e.g., elementary streams of the same program). Each elementary stream, in its Packetized Elementary Stream format, is assigned a unique "Packet ID" (PID). For example, the video elementary stream for a network television program may be assigned a PID of "10", and the audio elementary stream for that program may be assigned a PID of "23", and so on.
At the second level, one or more Packetized Elementary Streams may be further segmented or "packetized" to facilitate combining those streams into a single bitstream for transmission over some medium. Ultimately, two different "second level" protocols for combining one or more Packetized Elementary Streams into a single bitstream emerged: 1) the Program Stream (PS) protocol and 2) the Transport Stream protocol. Both stream protocols are packet-based and fall into the category of "transport layer" entities, as defined by the ISO Open System Interconnection (OSI) reference model. Program Streams utilize variable-length packets and are intended for "error-free" environments in which software parsing is desired. Program Stream packets are generally relatively large (1K to 2K bytes). Transport Streams utilize fixed length packets and are intended for transmission in noisy or errored environments. Each Transport Stream packet comprises a header portion and a payload portion. Transport Stream packets have a relatively short length of 188 bytes and include features for enhanced error resiliency and packet loss detection. The remaining background discussion will focus primarily on the MPEG-2 Transport Stream protocol.
As finally adopted, the Transport Stream protocol provides a standard format (i.e., syntax and set of semantic rules) for combining one or more Packetized Elementary Streams into a single "Transport Stream" that may then be transmitted over some medium. Essentially, the individual packets of each Packetized Elementary Stream are segmented and inserted into the payload sections of successive Transport Packets. That is/each Packetized Elementary Stream is inserted into a respective sequence of Transport Packets. The PID associated with a given Packetized Elementary Stream is then inserted into the headers of each Transport Packet that carries data from that Packetized Elementary Stream.
The Transport Packets formed from each Packetized Elementary Stream are then multiplexed to form a single outgoing bitstream or "Transport Stream." Thus, a Transport Stream comprises a continuous sequence of Transport Packets, each of which may carry data from one of a plurality of Packetized Elementary Streams. FIG. 1 graphically illustrates this two level multiplexing approach. As shown, an elementary stream 2, which may comprise a stream of coded video or audio data, is segmented and inserted into the payloads of a plurality of successive packets 4 to form a Packetized Elementary Stream. Each packet 4 of the Packetized Elementary Stream is then segmented and inserted into the payloads of a consecutive sequence of Transport Packets 6. The header of each Transport Packet 6 will contain the PID associated with that elementary stream 2.
As explained above, the Transport Packets formed from a number of different elementary streams are then multiplexed to form a single outgoing Transport Stream. At a decoder location, a given elementary stream can be recovered from the incoming Transport Stream by simply extracting every incoming Transport Packet whose header contains the PID assigned to that elementary stream. A group of related elementary streams (e.g. audio, video etc.) can be extracted to reproduce a complete "program." The two-level packet-based multiplexing approach of the MPEG-2 Systems standard can be used in a wide variety of applications. For example, such a multiplexing approach is particularly well suited for the transmission of audio and video programming in a subscription television system, such as a CATV or Direct Broadcast Satellite (DBS) system.
As originally proposed by Applicant and ultimately adopted by the MPEG-2 Systems Committee, each "program" (i.e., a combination of related elementary streams) carried in a given Transport Stream is assigned a unique "program number" to facilitate selection of a program for viewing at a decoder location. To facilitate extraction of a selected program from an incoming Transport Stream, a Program Map Table is transmitted to the decoder that contains a "program definition" for each user selectable program number. The program definition for a given program number identifies which elementary streams in the incoming Transport Stream "make-up" that program. Specifically, the program definition for a given program specifies the Packet IDs associated with each elementary stream of the selected program. For example, a television program will typically comprise a video elementary stream and an associated audio elementary stream. The program definition for that television program will contain two PID values, one that identifies the video elementary stream and one that identifies the audio elementary stream. Once the PID's are known, the decoder can simply extract every incoming Transport Packet whose header contains a PID that matches one of those listed in the program definition. The audio and video elementary stream data can then be recovered from the extracted Transport Packets and processed for output to a television or other device.
As the MPEG-2 Systems standard developed, it was suggested by members of the MPEG-2 Systems Committee that the standard accommodate encryption or scrambling of elementary stream data on an individual stream basis. Ultimately, the MPEG-2 Systems Committee decided that encryption of elementary stream data could be performed at the Transport Packet level. Specifically, when it is desired to encrypt a given elementary stream, rather than encrypting the elementary stream data in its raw form, encryption can be performed by encrypting the payload portion of each Transport Packet that carries data of that elementary stream.
At this point it is important to note that the MPEG-2 Systems standard does not dictate the mechanism or algorithm by which elementary streams are to be encrypted or scrambled. Rather, individual system vendors may employ their own proprietary encryption schemes. What the MPEG-2 Systems standard recognizes, however, is that any encryption or scrambling technique will require that encryption related information be transmitted to system decoders in order to facilitate decryption or descrambling at each decoder.
For example, it is expected that many vendors of MPEG-2 compliant transmission systems will implement private-key cryptographic techniques for uniquely encrypting different elementary streams. With private key cryptography, encryption control words (sometimes also referred to as encryption seeds) are generated at the encryption site and are used to "key" the encryption algorithm in order to produce a pseudo-random binary sequence, sometimes referred to as a "key stream". Many private key cryptographic systems are expected to employ the well known Data Encryption Standard (DES) algorithm. Encryption of a clear data stream, such as the elementary stream data in the payload section of a Transport Packet, is accomplished by combining the clear data with the key stream in a pre-defined manner, such as, for example, by performing a bitwise exclusive-OR operation on the two streams. In an MPEG-2 compliant system, unique encryption of each elementary stream can be achieved simply by employing different encryption control words for each elementary stream. Decryption of a given elementary stream at a decoder can only be performed if the decoder is provided with the encryption control words used to encrypt that elementary stream. Accordingly, it will be necessary in any MPEG-2 system that employs private key cryptography to provide a mechanism for transmitting encryption control words, and other encryption related information, to each decoder.
As development of the MPEG-2 Systems standard progressed, the MPEG-2 Systems Committee decided that encryption related information (sometimes referred to in the art as "conditional access information") would be transmitted to decoders in the form of Entitlement Control Messages (ECMs). Each ECM typically will contain encryption or scrambling related information for only one of the elementary streams in a given Transport Stream. As such, an ECM is stream-specific. For example, in a system employing a private-key cryptographic technique, an ECM may be used to transmit the encryption control words necessary for decrypting a particular elementary stream. ECMs for a given elementary stream may be transmitted in dedicated Transport Packets, or alternatively, may be transmitted in "adaptation fields" of the Transport Packets that carry that elementary stream. ECMs can be retrieved by a decoder in order to decrypt the elementary stream data of a user selected program.
It should be noted that the MPEG-2 Systems standard does not dictate the content or format of an ECM. The MPEG-2 Systems standard merely dictates how ECMs are to be transmitted within a given Transport Stream. Details of the encryption hardware and the content of an ECM are left to individual system vendors. Accordingly, a vendor supplying encoding and decoding equipment that operates in accordance with the MPEG-2 Systems standard may develop its own encryption scheme and associated ECM format.
Applicant and his Assignee have been actively involved in the development of the MPEG-2 Systems standard and have contributed to various aspects of the standard. As Applicant recognized during development of the encryption related aspects of the MPEG-2 Systems standard, because each ECM in a given Transport Stream relates to a particular elementary stream, a mechanism is needed for identifying which ECMs are associated with each elementary stream. For example, when a decoder begins extracting the Transport Packets that contain the elementary streams of a selected program, the decoder must be able to locate and extract the ECMs that contain the encryption related information necessary for descrambling or decrypting each of those elementary streams.
Applicant further recognized that in many applications, particularly subscription television applications, it is desirable to provide various decoders in the system with other decoder specific and/or system-wide "conditional access" information. For example, it is often desirable to transmit authorization information to various decoders or groups of decoders for controlling access to different programs or tiers of programs in a given Transport Stream. Recognizing the need to provide such decoder specific and/or system wide conditional access information to decoders, it was suggested by the MPEG-2 Systems Committee that such information could be transmitted to decoders in the form of Entitlement Management Messages (EMMs), which would be similar to the ECMs used to transmit stream-specific conditional access information. The concept of an Entitlement Management Message is well known in the prior art. Applicant realized, however, that in a typical application, such as a subscription television application, it is likely that a number of different vendors might provide decoders to different subscribers in the same system. Each vendor's decoder will most likely operate in accordance with that vendor's own proprietary conditional access subsystem. Consequently, it will be necessary to transmit different EMM streams to support each of the different conditional access systems being employed. As a result, a mechanism will be needed for directing each decoder to the appropriate EMMs carried in a given Transport Stream.
Applicant's invention addresses both of the foregoing needs by providing novel methods for locating conditional access information transmitted in a packet-based multiplexed communications system, such as an MPEG-2 compliant communications system. Applicant, on behalf of his Assignee, proposed the methods of the present invention for inclusion in the MPEG-2 Systems standard, and the methods of the present invention, as defined by the appended claims, were substantially adopted as part of the MPEG-2 Systems standard. Applicant described his proposal in a paper presented to the International Standards Organization (ISO), entitled "Syntax Proposal for MPEG-2 Transport Stream Program Specific Information", ISO/IEC JTC1/SC29/WG11 MPEG 93/612 (July, 1993), which is hereby incorporated by reference.